package x.y.z;

public class Interview_4_12_PathsWithSum {
    public int pathSum(TreeNode root, int sum) {
        if (root == null) {
            return 0;
        }
        int pathFromRoot = countPathWithSumFromNode(root, sum, 0);
        int left = pathSum(root.left, sum);
        int right = pathSum(root.right, sum);
        return pathFromRoot + left + right;
    }

    public int countPathWithSumFromNode(TreeNode root, int targetSum, int currentSum) {
        if (root == null) {
            return 0;
        }
        currentSum += root.val;
        int totalPath = 0;
        if (currentSum == targetSum) {
            totalPath++;
        }
        totalPath += countPathWithSumFromNode(root.left, targetSum, currentSum);
        totalPath += countPathWithSumFromNode(root.right, targetSum, currentSum);
        return totalPath;
    }
}
